// BestTimeBuyAndSellStockIII.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <vector>
using namespace std;
//Say you have an array for which the ith element is the price of a given stock on day i.

//Design an algorithm to find the maximum profit. You may complete at most two transactions.

//Note:
//You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

int maxProfit(vector<int> &prices)
{
	if(prices.size() <= 0)
		return 0;
	vector<int> historyProfit;
    vector<int> futureProfit;
	int len = prices.size();
    historyProfit.assign(len,0);
    futureProfit.assign(len,0);
    int valley = prices[0];
    int peak = prices[len-1];
    int maxProfit = 0;
	// forward, calculate max profit until this time
    for (int i = 1; i<len; ++i)
    {
        valley = min(valley,prices[i]);
        historyProfit[i]=max(historyProfit[i-1],prices[i]-valley);
    }

	// backward, calculate max profit from now, and the sum with history
    for (int i = len-2; i>=0; --i)
    {
        peak = max(peak, prices[i]);
		futureProfit[i]=max(futureProfit[i+1],peak-prices[i]);
        maxProfit = max(maxProfit,historyProfit[i]+futureProfit[i]);
    }
	return maxProfit;
}

int _tmain(int argc, _TCHAR* argv[])
{
	return 0;
}

